package com.iqik.base.alg;

import java.util.ArrayList;
import java.util.List;

public class NodeDemo {
    static class Node {
        Node next;
        int data;
        public Node(int data) {
            this.data = data;
        }

    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        print(node1);
        arrange(node1);
        print(node1);
    }

    static void TwoNum()
    {
        int AShi;
        int AGe;
        int Bshi;
        int Bge;

        for (int num = 10; num < 100; num++)
        {
            for (int n = num + 1; n < 100; n++)
            {
                AShi = num / 10;
                AGe = num % 10;
                Bshi = n / 10;
                Bge = n % 10;

                //ac=bd
                if (AShi * Bshi == AGe * Bge)
                {
                    System.out.println("两个数为  "+AShi + ""+ AGe + "， "+ Bshi + ""+ Bge);
                }
            }
        }
    }


    /**
     * 遍历打印出整个单链表
     */
    public static void print(Node root) {
        Node node = root;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    /**
     * 重新排列单链表
     */
    public static Node arrange(Node root) {
        // 遍历单链表，并存储到一个有序集合中，因为不明确单链表的长度，这里采用List集合
        List<Node> nodes = new ArrayList<>();
        Node tmp = root;
        while (tmp != null) {
            nodes.add(tmp);
            tmp = tmp.next;
        }
        Node target = null;
        for (int i = 0; i < nodes.size() / 2; i++) {
            //如果是第一个元素则当前节点为i所在节点
            //如果不是第一个元素，当前节点此时为上一次操作的最后一个元素
            //此时需要把当前节点指向i所在节点
            if (target == null){
                target = nodes.get(i);
            } else {
                target.next = nodes.get(i);
                target = nodes.get(i);
            }
            //获取列表另一半对应的尾结点
            Node last = nodes.get(nodes.size() - i - 1);
            if (last != null) {
                target.next = last;
                //每次把last的指向设置为空
                last.next = null;
            }
            //将操作的后一半节点设置为当前节点
            target = last;
            //如果单链表的个数为奇数，则在最后一次遍历的时候把最后一个节点指向中间节点
            if (i == nodes.size() / 2 - 1 && nodes.size() % 2 != 0 && target != null) {
                Node middle = nodes.get(nodes.size() / 2);
                target.next = middle;
                middle.next = null;
            }
        }
        return nodes.get(0);
    }
}
